Merge Two Sorted Lists

LeetCode 21 | Difficulty: Easy

Easy

Problem Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

- The number of nodes in both lists is in the range `[0, 50]`.

- `-100 <= Node.val <= 100`

- Both `list1` and `list2` are sorted in **non-decreasing** order.

Topics: Linked List, Recursion

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	24.7 MB
Date	2019-12-15

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(Int32.MaxValue);
        ListNode tail = dummy;
        if(l1 == null && l2 != null) return l2;
        if(l1 != null && l2 == null) return l1;

        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                tail.next = l1;
                l1 = l1.next;
            }
            else
            {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;           
        }
        tail.next = (l1==null) ? l2 : l1;
        return dummy.next;
    }
}

📜 1 more C# submission(s)

Submission (2017-07-24) — 155 ms, N/A

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(Int32.MaxValue);
        ListNode tail = dummy;
        if(l1 == null && l2 != null) return l2;
        if(l1 != null && l2 == null) return l1;

        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                tail.next = l1;
                l1 = l1.next;
            }
            else
            {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;           
        }
        tail.next = (l1==null) ? l2 : l1;
        return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.